def FindMaximumSubarray(A,low,high):
    '''

    :param A: 需要找到最大子集的序列
    :param low: 最小参数
    :param high: 最大参数
    :return: 最大子集的范围和最大子集和
    '''
    #base case:当只有序列长度为1的情况
    if high == low:
        return (low,high,A[low])
    else:
        mid = (low + high)//2
        #计算左边序列的最大值，为原问题的一个子问题
        (left_low, left_high, left_sum) = FindMaximumSubarray(A, low, mid)
        #计算右边序列的最大值，为原问题的一个子问题
        (right_low, right_high, right_sum) = FindMaximumSubarray(A, mid+1, high)
        #计算跨过mid序列的最大值
        (cross_low, cross_high, cross_sum) = FindMaxCrossingSubarray(A, low, mid, high)
    #判断最大值
    if left_sum<0 and right_sum<0 and cross_sum<0:#Problem4.1-4
        return (-1, -1, 0)
    elif left_sum >= right_sum and left_sum >= cross_sum:
        return (left_low, left_high, left_sum)
    elif right_sum >= left_sum and right_sum >= cross_sum:
        return (right_low, right_high, right_sum)
    else:
        return (cross_low, cross_high, cross_sum)
def FindMaxCrossingSubarray(A, low, mid, high):
    '''

    :param A: array
    :param low: left index
    :param mid: mid index
    :param high: right index
    :return: 最大子集的范围和最大子集和
    '''
    left_sum = -float('inf')
    sum = 0
    for i in range(mid,low-1,-1):
        sum=sum+A[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i
    right_sum = -float('inf')
    sum=0
    for i in range(mid+1,high+1):
        sum=sum+A[i]
        if sum > right_sum:
            right_sum = sum
            max_right = i


    return (max_left, max_right, left_sum+right_sum)
# if __name__ == '__main__':
#     A=[1,-4,3,-4]
#     print(FindMaximumSubarray(A,0,3))
#     B = [-1, -2, -3, -4]
#     print(FindMaximumSubarray(B, 0, 3))
